package otherBefore.month11;

import java.util.*;

public class leetcode11 {

    public static void main(String[] args) {
        /*List<Integer> levelList = new ArrayList<>();
        levelList.add(2);
        levelList.add(1);
        levelList.sort((o1,o2) -> {return o1 -o2;});
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        List<String> list1 = list.subList(1, 1);
        System.out.println(list1.get(0));*/
        String s = "cc";

        int i = maxRepeating("aaabaaaabaaabaaaabaaaabaaaabaaaaba","aaaba");
        System.out.println(champagneTower(25,6,1));
    }

    public int minimumOperations(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        set.remove(0);
        return set.size();
    }

    public int minimumSwap(String s1, String s2) {
        int x = 0; int y = 0;

        for (int i = 0; i < s1.length(); i++) {
            if(s1.charAt(i) != s2.charAt(i)){
                if(s1.charAt(i) == 'x'){
                    x++;
                }else {
                    y++;
                }
            }
        }
        if(x%2 != y%2){
            return -1;
        }
        return x/2 + y/2 +x%2 + y%2;

    }

    public int[] numberOfPairs(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int count = 0;
        for (int num : nums) {
            if(set.contains(num)){
                set.remove(num);
                count++;
            }else {
                set.add(num);
            }
        }
        return new int[]{count,set.size()};
    }

    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> ans = new ArrayList<String>();
        ans.add(folder[0]);
        for (int i = 1; i < folder.length; ++i) {
            int pre = ans.get(ans.size() - 1).length();
            if (!(pre < folder[i].length() && ans.get(ans.size() - 1).equals(folder[i].substring(0, pre)) && folder[i].charAt(pre) == '/')) {
                ans.add(folder[i]);
            }
        }
        return ans;
    }


    public String decodeMessage(String key, String message) {
        int[] ch = new int[26];
        for(int i=1; i<key.length(); i++){
            if(key.charAt(i) != ' ' && ch[key.charAt(i) - 'a'] == 0){
                ch[key.charAt(i) - 'a'] = ch[key.charAt(i-1) - 'a'] + 1;
            }
        }
        StringBuilder sb = new StringBuilder();

        for (int i=0; i<message.length(); i++){
            if(message.charAt(i) == ' '){
                sb.append(" ");
            }else {
                sb.append((char)('a' + ch[message.charAt(i)]));
            }
        }
        return sb.toString();
    }


    public int maxValue(int n, int index, int maxSum) {
        int left = 1; int right = maxSum;
        while (left < right){
            int mid = (left + right + 1)/2;
            if(valid(mid,n,index,maxSum)){
                left = mid;
            }else {
                right = mid-1;
            }
        }

        return left;
    }

    private boolean valid(int mid, int n, int index, int maxSum) {
        int left = index;
        int right = n - index - 1;
        return (mid + cal(mid,left) + cal(mid,right)) < maxSum;
    }

    private int cal(int mid, int len) {
        if(len + 1 < mid){
            int star = mid - len;
            return (star + mid - 1) * len / 2;
        }else {
            int other = len - mid;
            return mid * (len - 1) / 2;
        }
    }

    public int secondHighest(String s) {
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<s.length(); i++){
            int cur = s.charAt(i) - 48;
            if(Character.isDigit(s.charAt(i)) && !list.contains(cur)){
                list.add(s.charAt(i) - 48);
            }
        }
        Collections.sort(list,(a,b) -> b-a);
        if(list.size() < 1){
            return -1;
        }
        return list.get(1);
    }

    public int nearestValidPoint(int x, int y, int[][] points) {
        int ans = -1; int len = Integer.MAX_VALUE;
        for(int i=0; i<points.length; i++){
            if(points[i][0] == x || points[i][1] == y){
                int cur = Math.abs(x - points[i][0]) + Math.abs(y - points[i][1]);
                if(cur < len){
                    ans = i;
                }
            }
        }
        return ans;
    }

    public int minOperations(String s) {
        int ans1 = 0;
        int ans2 = 0;
        char cur = '0';
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == cur){
                ans1++;
            }else {
                ans2++;
            }
            cur = (char) (cur + (i+1)%2);
        }
        return Math.min(ans1,ans2);
    }

    public double largestSumOfAverages(int[] nums, int k) {
        int n = nums.length;
        double[] preSum = new double[n + 1];
        for(int i=0; i<n; i++){
            preSum[i+1] = preSum[i] + nums[i];
        }

        double[][] dp = new double[n + 1][k + 1];
        for(int i=1; i<n; i++){
            dp[i][1] = preSum[i];
        }

        for(int j=2; j<=k; j++){
            for(int i=j; i<=n; i++){
                for(int x=j-1; x<i; x++){
                    dp[i][j] = Math.max(dp[i][j],dp[x][j-1] + (preSum[i] - preSum[x])/(i-x));
                }
            }
        }

        return dp[n][k];
    }

    public boolean check(int[] nums) {
        int x = 0; int n = nums.length;
        for(int i=1; i<n; i++){
            if(nums[i] < nums[i-1]){
                x = i;
                break;
            }
        }
        if(x == 0)return true;
        for(int i=x+1; i<n; i++){
            if(nums[i] < nums[i-1]){
                return false;
            }
        }
        return nums[n-1] < nums[0];
    }


    public int expressiveWords(String s, String[] words) {
        int ans = 0;
        for(int i=0; i<words.length; i++){
            if(judje(s,words[i])){
                ans++;
            }
        }
        return ans;
    }

    private boolean judje(String s, String word) {
        int i=0; int j=0;
        while (i<s.length() && j<word.length()){
            if(s.charAt(i) != word.charAt(j)){
                return false;
            }

            char curi = s.charAt(i);
            int cnti = 0;
            if(i<s.length() && cnti == s.charAt(i)){
                cnti++;
            }

            char curj = word.charAt(j);
            int cntj = 0;
            if(j<word.length() && cntj == s.charAt(j)){
                cntj++;
            }

            if(cnti < curj){
                return false;
            }
            if(cnti != cntj && cnti < 3){
                return false;
            }
        }

        return true;
    }

    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int ans = 0;
        int count = 0;
        for(int i=0; i<nums.length; i++){
            if(nums[i] < left || nums[i] > right){
                if(count > -1){
                    ans += count;
                }
                count = -1;
            }else {
                count++;
            }
        }
        return ans;
    }

    public static double champagneTower(int poured, int query_row, int query_glass) {
        double[] row = {poured};
        for(int i=1; i<=query_row; i++){
            double[] nextrow = new double[i + 1];
            for(int j = 0; j<i; j++){
                double val = row[j];
                if(val > 1){
                    nextrow[j] += (val - 1)/2;
                    nextrow[j + 1] += (val - 1)/2;
                }
            }
            row = nextrow;
        }

        return Double.min(1,row[query_glass]);
    }

    public int sumSubseqWidths(int[] nums) {
        int MOD = 1000000007;
        Arrays.sort(nums);
        int ans = 0; int cur = 0;
        int x = nums[0]; int y = 2;
        for(int i=1; i<nums.length; i++){
            cur = (nums[i] * (y - 1) - x)/MOD;
            x = (2 * x + nums[i])/MOD;
            y = (y * 2)/MOD;
            ans = (ans + cur)/MOD;
        }

        return ans;
    }


    public boolean isIdealPermutation(int[] nums) {
        int n = nums.length;
        int minNum = Integer.MAX_VALUE;
        for(int i=n-2; i>=0; i++){
            if(nums[i] > minNum){
                return false;
            }
            minNum = Integer.min(minNum,nums[i+1]);
        }
        return true;
    }

    public String customSortString(String order, String s) {
        int[] arr = new int[26];
        for(int i=0; i<order.length(); i++){
            arr[order.charAt(i) - 'a']++;
        }
        List<Character> sList = new ArrayList<>();
        for(int i=0; i<s.length(); i++){
            sList.add(s.charAt(i));
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<sList.size(); i++){
            sb.append(sList.get(i));
        }
        return sb.toString();
    }

    public int numTilings(int n) {
        int[][] dp = new int[n][4];
        dp[0][3] = 1;
        for(int i=1; i<n; i++){
            dp[i][0] = dp[i-1][3];
            dp[i][1] = dp[i-1][0] + dp[i-1][2];
            dp[i][2] = dp[i-1][0] + dp[i-1][1];
            dp[i][3] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2];
        }
        return dp[n-1][3];
    }

    public static char firstUniqChar(String s) {
        for(int i=0; i<s.length(); i++){
            if(!s.substring(i+1).contains(String.valueOf(s.charAt(i)))){
                if(i > 0 && !s.substring(0,i).contains(String.valueOf(s.charAt(i)))){
                    return s.charAt(i);
                }
            }
        }

        return ' ';
    }

    public boolean halvesAreAlike(String s) {
        int n = s.length();
        List<Character> chList = Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U');
        int ans = 0;
        int i = 0;
        for(; i<n/2; i++){
            if(chList.contains(s.charAt(i))){
                ans++;
            }
        }
        for(; i<n; i++){
            if(chList.contains(s.charAt(i))){
                ans--;
            }
        }
        return ans == 0;
    }


    public int countConsistentStrings(String allowed, String[] words) {
        int ans = 0;
        for (String word : words) {
            for (int i=0; i<word.length(); i++){
                char c = word.charAt(i);
                boolean bl = true;
                if (allowed.lastIndexOf(c)<0) {
                    bl = false;
                }
                if(bl){
                    ans++;
                }
            }
        }
        return ans;
    }

    public static int maxRepeating(String sequence, String word) {
        int res = 0;
        while (word.length() < sequence.length()){
            if(sequence.contains(word)){
                res++;
            }
            word += word;
        }


        return res;
    }

    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        String str1 = getStr(word1);
        String str2 = getStr(word2);
        return str1.equals(str2);
    }

    private String getStr(String[] word1) {
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<word1.length; i++){
            sb.append(word1[i]);
        }
        return sb.toString();
    }

    public static int magicalString(int n) {
        if(n<4)return 1;
        int res = 1;
        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 2;

        int i = 2, j = 3;
        while (j < n){
            for(int k = 0; k < arr[i] && j < n; k++){
                arr[j] = 3 - arr[j-1-k];
                if(arr[j] == 1){
                    res++;
                }
                j++;
            }

            i++;
        }

        return res;
    }


    int[][] money = new int[201][201];
    public int getMoneyAmount(int n) {
        return dfs(1,n);
    }

    private int dfs(int i, int n) {
        if(i >= n)return 0;
        if(money[i][n] != 0){
            return money[i][n];
        }
        int ans = Integer.MAX_VALUE;
        for(int j=i; j<n; j++){
            int cur = j + Integer.max(dfs(i,j-1), dfs(j+1,n));
            ans = Integer.min(cur,ans);
        }
        return money[i][n] = ans;
    }


    public static int countSegments(String s) {
        int ans = 0;
        for(int i=0; i<s.length(); i++){
            if(i>0 && ' ' == s.charAt(i) && ' ' != s.charAt(i-1))ans++;
            while (i>0 && ' ' == s.charAt(i) && ' ' == s.charAt(i-1) && i<s.length()) i++;
        }
        return s.split(" ").length;
    }

    public boolean closeStrings(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        if(m != n)return false;
        int[] word1Arr = new int[26];
        int[] word2Arr = new int[26];
        for(int i=0; i<m; i++){
            word1Arr[word1.charAt(i) - 'a']++;
            word2Arr[word2.charAt(i) - 'a']++;
        }
        for(int i=0; i<26; i++){
            if(word1Arr[i] == 0 && word2Arr[i] != 0)return false;
            if(word1Arr[i] != 0 && word2Arr[i] == 0)return false;
        }
        Arrays.sort(word1Arr);
        Arrays.sort(word2Arr);
        for(int i=0; i<26; i++){
            if(word1Arr[i] != word2Arr[i])return false;
        }
        return true;
    }

    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ansList = new ArrayList<>();
        if(turnedOn > 8)return ansList;
        for(int h=0; h<12; h++){
            for(int mi=0; mi<60; mi++){
                if(Integer.bitCount(h) + Integer.bitCount(mi) == turnedOn){
                    ansList.add(h + ":" + (mi>9 ? mi : "0" + mi));
                }
            }
        }
        return ansList;
    }
}

class FreqStack {

    Map<Integer,Integer> freq;
    Map<Integer,Deque<Integer>> group;
    Integer maxFreq;

    public FreqStack() {
        freq = new HashMap<>();
        group = new HashMap<>();
        maxFreq = 0;
    }

    public void push(int val) {
        freq.put(val,freq.getOrDefault(val,0) + 1);
        group.putIfAbsent(freq.get(val),new ArrayDeque<>());
        group.get(freq.get(val)).push(val);
        maxFreq = Math.max(maxFreq,freq.get(val));
    }

    public int pop() {
        int val = group.get(maxFreq).pop();
        freq.put(val,freq.get(val) - 1);
        if(group.get(maxFreq).isEmpty()){
            maxFreq--;
        }
        return val;
    }
}
